package Hot100.Medium.GreedyAndDP.Greedy;

public class LC621 {
    public static void main(String[] args) {

    }

    public int leastInterval(char[] tasks, int n) {
        int[] cnts = new int[26];
        for (char c : tasks) {
            cnts[c - 'A']++; // 统计tasks中各个字母出现的次数
        }
        int max = 0, tot = 0; // max表示出现次数最多的任务数量
        for (int i = 0; i < 26; i++) max = Math.max(max, cnts[i]);

        // 统计有多少任务达到了最大次数，tot 表示有多少个任务的出现次数等于 max。
        for (int i = 0; i < 26; i++) {
            if(max == cnts[i]){
                tot = tot + 1;
            }
        }
        // 用图形理解，每个最频繁的任务（除最后一组外）需要间隔 n，所以 (max - 1) 组。
        // 每组占 (n + 1) 个时间（1 个任务本身 + n 个间隔）。
        // 最后一组的任务数是 tot
        int res = (n + 1) * (max - 1) + tot ;
        return Math.max(tasks.length, res);
    }
}
